package oj;

//相同的树：给你两棵二叉树的根节点 p 和 q ，编写一个函数来检验这两棵树是否相同。如果两个树在结构上相同，并且节点具有相同的值，则认为它们是相同的。
public class Solution_100 {
    public boolean isSameTree(TreeNode p, TreeNode q) {
        //两棵树是否为空
        if(p == null && q == null){
            return true;
        }

        //只能是以下三种情况：
        //(1) p == null && q != null
        //(2) p != null && q == null
        //(3) p != null && q != null

        if(p == null || q == null){
            //一定是第一种或者第二种情况
            return false;
        }

        //都不为空时：
        //两棵树相同：根的值相同 + 左子树相同 + 右子树相同

        if(p.val != q.val){
            //根不一样就不需要再比较左右子树
            return false;
        }
        boolean r = isSameTree(p.left,q.left);
        if(r == false){
            //说明两棵树的左子树不相同，没有继续比较的必要
            return false;
        }
        r = isSameTree(p.right,q.right);
        if(r == true){
            return true;
        }else{
            return false;
        }
        //可以直接写为：
        //return p.val == q.val && isSameTree(p.left,q.left) && isSameTree(p.right,q.right);
    }
}
